#include <config.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "bignum.h"
#include "sbignum.h"

static uint8_t data_zero[1] = {0};
static uint8_t data_one[1] = {1};
static uint8_t data_two[1] = {2};
static uint8_t data_three[1] = {3};
static uint8_t data_four[1] = {4};
static uint8_t data_five[1] = {5};
static uint8_t data_six[1] = {6};
bignum_t bignum_zero = {
    1, data_zero
};
bignum_t bignum_one = {
    1, data_one
};
bignum_t bignum_two = {
    1, data_two
};
bignum_t bignum_three = {
    1, data_three
};
bignum_t bignum_four = {
    1, data_four
};
bignum_t bignum_five = {
    1, data_five
};
bignum_t bignum_six = {
    1, data_six
};

void bignum_free(bignum_t* num) {
    if (num->size != -1) {
        free(num->data);
    } else {
        // Try to free a bignum which is already freed
        abort();
    }
    num->size = -1;
}

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define INIT_BIGNUM(num, init_size)               \
    (num).data = malloc(init_size);               \
    if ((num).data == NULL)                       \
        abort();                                  \
    (num).size = (init_size);
#define RESIZE_BIGNUM(num, new_size)              \
    (num).size = (new_size);                      \
    (num).data = realloc((num).data, (num).size); \
    if ((num).data == NULL)                       \
        abort();

// 大数比较函数，返回 1 表示 a > b，返回 0 表示 a = b，返回 -1 表示 a < b
int bignum_compare(bignum_t* a, bignum_t* b) {
    int32_t size = MAX(a->size, b->size);
    int32_t pos_a = size, pos_b = size;
    for (int32_t i = 0; i < size; i++) {
        pos_a--, pos_b--;
        uint8_t num_a = 0, num_b = 0;
        if (pos_a < a->size) {
            num_a = a->data[pos_a];
        }
        if (pos_b < b->size) {
            num_b = b->data[pos_b];
        }
        if (num_a != num_b) {
            return num_a - num_b;
        }
    }
    return 0;
}

//计算一个大数的最高有效位的位置，从0开始计数，如果大数为0，返回-1
int bignum_hibit(bignum_t* a) {
    if(a == NULL) {
        return -1;
    }
    //从高字节开始扫描
    for(int i = a->size - 1; i >= 0; i--) {
        if(a->data[i] != 0) {
            //找到第一个非零字节
            int bit = 7; //从高位开始扫描
            while ((a->data[i] & (1 << bit)) == 0) {
                //找到第一个非零位
                bit--;
            }
            return i * 8 + bit; //返回位的位置
        }
    }
    return -1; //大数为0
}

// 高效交换两个 bignum
void bignum_swap(bignum_t* a, bignum_t* b) {
    bignum_t tmp;
    tmp.size = a->size;
    tmp.data = a->data;
    a->size = b->size;
    a->data = b->data;
    b->size = tmp.size;
    b->data = tmp.data;
}

// 将大数b的值复制到a上，且a未分配空间
void bignum_cpy(bignum_t* a, bignum_t* b) {
    if (b == NULL) {
        return;
    }
    INIT_BIGNUM(*a, b->size);
    memcpy(a->data, b->data, b->size);
}

void bignum_add(bignum_t* p, bignum_t* q, bignum_t* res) {
    // 总共进行加法的字节数
    int32_t size = MAX(p->size, q->size);
    // p 和 q 都可以相加的字节数
    int32_t left_size = MIN(p->size, q->size);
    // 目前相加到的位置
    int32_t pos = 0;

    res->size = size + 1;
    res->data = malloc(res->size);
    assert(res->data != NULL);

    // 只有进位和不进位两种可能
    int overflow = 0;
    while (size > 0) {
        // 根据剩余大小决定进行的加法长度
#ifdef HAVE_UINT64_T
        if (left_size >= 8 || (left_size == 0 && size - left_size >= 8)) {
            uint64_t p_data = 0, q_data = 0;
            // 根据 p 和 q 的剩余大小提取数字
            if (p->size > pos) {
                p_data = *((uint64_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint64_t*)&q->data[pos]);
            }
            uint64_t data = p_data + q_data + overflow;
            if (p_data == UINT64_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT64_MAX - q_data;
            }
            *((uint64_t*)&res->data[pos]) = *((uint64_t*)&data);
            pos += 8;
            size -= 8;
            left_size = MAX(left_size - 8, 0);
        } else
#endif
        if (left_size >= 4 || (left_size == 0 && size - left_size >= 4)) {
            uint32_t p_data = 0, q_data = 0;
            // 根据 p 和 q 的剩余大小提取数字
            if (p->size > pos) {
                p_data = *((uint32_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint32_t*)&q->data[pos]);
            }
            uint32_t data = p_data + q_data + overflow;
            if (p_data == UINT32_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT32_MAX - q_data;
            }
            *((uint32_t*)&res->data[pos]) = *((uint32_t*)&data);
            pos += 4;
            size -= 4;
            left_size = MAX(left_size - 4, 0);
        } else if (left_size >= 2 || (left_size == 0 && size - left_size >= 2)) {
            uint16_t p_data = 0, q_data = 0;
            if (p->size > pos) {
                p_data = *((uint16_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint16_t*)&q->data[pos]);
            }
            uint16_t data = p_data + q_data + overflow;
            if (p_data == UINT16_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT16_MAX - q_data;
            }
            *((uint16_t*)&res->data[pos]) = *((uint16_t*)&data);
            pos += 2;
            size -= 2;
            left_size = MAX(left_size - 2, 0);
        } else {
            uint8_t p_data = 0, q_data = 0;
            if (p->size > pos) {
                p_data = *((uint8_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint8_t*)&q->data[pos]);
            }
            uint8_t data = p_data + q_data + overflow;
            if (p_data == UINT8_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT8_MAX - q_data;
            }
            *((uint8_t*)&res->data[pos]) = *((uint8_t*)&data);
            pos += 1;
            size -= 1;
            left_size = MAX(left_size - 1, 0);
        }
    }
    // 最后一位设置为进位值
    if (overflow == 0) {
        res->size--;
    } else {
        res->data[res->size - 1] = (uint8_t)overflow;
    }
}

// p += q
void bignum_inc(bignum_t* p, bignum_t* q) {
    int32_t p_size = p->size;
    // 总共进行加法的字节数
    int32_t size = MAX(p_size, q->size);
    RESIZE_BIGNUM(*p, size + 1);
    // p 和 q 都可以相加的字节数
    int32_t left_size = MIN(p_size, q->size);
    // 目前相加到的位置
    int32_t pos = 0;

    // 只有进位和不进位两种可能
    int overflow = 0;
    while (size > 0) {
        // 根据剩余大小决定进行的加法长度
#ifdef HAVE_UINT64_T
        if (left_size >= 8 || (left_size == 0 && size - left_size >= 8)) {
            uint64_t p_data = 0, q_data = 0;
            // 根据 p 和 q 的剩余大小提取数字
            if (p_size > pos) {
                p_data = *((uint64_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint64_t*)&q->data[pos]);
            }
            uint64_t data = p_data + q_data + overflow;
            // p + q > UINT64_MAX 等同于 p > UINT64_MAX - q
            if (p_data == UINT64_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT64_MAX - q_data;
            }
            *((uint64_t*)&p->data[pos]) = *((uint64_t*)&data);
            pos += 8;
            size -= 8;
            left_size = MAX(left_size - 8, 0);
        } else
#endif
        if (left_size >= 4 || (left_size == 0 && size - left_size >= 4)) {
            uint32_t p_data = 0, q_data = 0;
            // 根据 p 和 q 的剩余大小提取数字
            if (p_size > pos) {
                p_data = *((uint32_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint32_t*)&q->data[pos]);
            }
            uint32_t data = p_data + q_data + overflow;
            // p + q > UINT32_MAX 等同于 p > UINT32_MAX - q
            if (p_data == UINT32_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT32_MAX - q_data;
            }
            *((uint32_t*)&p->data[pos]) = *((uint32_t*)&data);
            pos += 4;
            size -= 4;
            left_size = MAX(left_size - 4, 0);
        } else if (left_size >= 2 || (left_size == 0 && size - left_size >= 2)) {
            uint16_t p_data = 0, q_data = 0;
            if (p_size > pos) {
                p_data = *((uint16_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint16_t*)&q->data[pos]);
            }
            uint16_t data = p_data + q_data + overflow;
            if (p_data == UINT16_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT16_MAX - q_data;
            }
            *((uint16_t*)&p->data[pos]) = *((uint16_t*)&data);
            pos += 2;
            size -= 2;
            left_size = MAX(left_size - 2, 0);
        } else {
            uint8_t p_data = 0, q_data = 0;
            if (p_size > pos) {
                p_data = *((uint8_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint8_t*)&q->data[pos]);
            }
            uint8_t data = p_data + q_data + overflow;
            if (p_data == UINT8_MAX && overflow) {
                overflow = 1;
            } else {
                overflow = p_data + overflow > UINT8_MAX - q_data;
            }
            *((uint8_t*)&p->data[pos]) = *((uint8_t*)&data);
            pos += 1;
            size -= 1;
            left_size = MAX(left_size - 1, 0);
        }
    }
    // 最后一位设置为进位值
    if (overflow == 0) {
        p->size--;
    } else {
        p->data[p->size - 1] = (uint8_t)overflow;
    }
}

void bignum_sub(bignum_t* p, bignum_t* q, bignum_t* res) { // 结果只返回正数,
    int32_t size = p->size;                   //进行减法的字节数
    int32_t left_size = q->size;              //可以相减的位数
    int32_t pos = 0;                          // 当前相减的位置
    
    if (left_size > size) {
        left_size = size;
    }

    res->size = size;
    res->data = malloc(size);
    assert(res->data != NULL);
    uint8_t pre_flag = 0;                      //判断是否借位
    uint8_t now_flag = 0;
    while (size > 0) {
        //根据剩余大小决定相减的位数
#ifdef HAVE_UINT64_T
        if (left_size >= 8 || (left_size == 0 && size - left_size >= 8)) {//八个字节八个字节的相减
            uint64_t p_data = 0, q_data = 0, data = 0;
            if(p->size > pos){
                p_data = *((uint64_t*)&p->data[pos]);
            }
            if(q->size > pos){
                q_data = *((uint64_t*)&q->data[pos]);
            }
            if((p_data - pre_flag < q_data) || ((p_data == q_data) && (pre_flag == 1))){
                now_flag = 1;
            }
            if(now_flag){
                data = p_data + (UINT64_MAX - q_data ) - pre_flag + 1; 
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint64_t*)&res->data[pos]) = *((uint64_t*)&data);
            size -= 8;
            pos += 8;
            left_size = MAX(left_size - 8, 0);
            now_flag = 0;
        } else
#endif
        if(left_size >= 4 || (left_size == 0 && size - left_size >= 4)){
            uint32_t p_data = 0, q_data = 0, data = 0;
            if(p->size > pos){
                p_data = *((uint32_t*)&p->data[pos]);
            }
            if(q->size > pos){
                q_data = *((uint32_t*)&q->data[pos]);
            }
            if((p_data - pre_flag < q_data) || ((p_data == q_data) && (pre_flag == 1))){
                now_flag = 1;
            }
            if(now_flag){
                data = p_data + (UINT32_MAX - q_data) - pre_flag + 1;
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint32_t*)&res->data[pos]) = *((uint32_t*)&data);
            size -= 4;
            pos += 4;
            left_size = MAX(left_size - 4, 0);
            now_flag = 0;
        } else if (left_size >= 2 || (left_size == 0 && size - left_size >= 2)){
            uint16_t p_data = 0, q_data = 0, data = 0;
            if(p->size > pos){
                p_data = *((uint16_t*)&p->data[pos]);
            }
            if(q->size > pos){
                q_data = *((uint16_t*)&q->data[pos]);
            }
            if((p_data - pre_flag < q_data) || ((p_data == q_data) && (pre_flag == 1))){
                now_flag = 1;
            }
            if(now_flag){
                data = p_data + (UINT16_MAX - q_data) - pre_flag + 1;
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint16_t*)&res->data[pos]) = *((uint16_t*)&data);
            size -= 2;
            pos += 2;
            left_size = MAX(left_size - 2, 0);
            now_flag = 0;
        } else {
            uint8_t p_data = 0, q_data = 0, data = 0;
            if(p->size > pos){
                p_data = *((uint8_t*)&p->data[pos]);
            }
            if(q->size > pos){
                q_data = *((uint8_t*)&q->data[pos]);
            }
            if((p_data - pre_flag < q_data) || ((p_data == q_data) && (pre_flag == 1))){
                now_flag = 1;
            }
            if(now_flag){
                data = p_data + (UINT8_MAX - q_data) - pre_flag + 1;
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint8_t*)&res->data[pos]) = *((uint8_t*)&data);
            size -= 1;
            pos += 1;
            left_size = MAX(left_size - 1, 0);
            now_flag = 0;
        }
    }
}

void bignum_dec(bignum_t* p, bignum_t* q) {//大数减法，将结果保存至bignum_t *q中
    int32_t size = p->size;      // 进行减法的字节数
    int32_t left_size = q->size; // 可以相减的位数

    if (left_size > size) {
        left_size = size;
    }

    int32_t pos = 0;             // 当前相减的位置
    uint8_t pre_flag = 0; // 判断是否借位
    uint8_t now_flag = 0;
    while (size > 0) {
        // 根据剩余大小决定相减的位数
#ifdef HAVE_UINT64_T
        if (left_size >= 8 || (left_size == 0 && size - left_size >= 8)) { // 八个字节八个字节的相减
            uint64_t p_data = 0, q_data = 0, data = 0;
            if (p->size > pos) {
                p_data = *((uint64_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint64_t*)&q->data[pos]);
            }
            if ((p_data < q_data + pre_flag) || ((p_data == q_data) && (pre_flag == 1))) {
                now_flag = 1;
            }
            if (now_flag) {
                data = p_data + (UINT64_MAX - q_data) - pre_flag + 1;
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint64_t*)&p->data[pos]) = *((uint64_t*)&data);
            size -= 8;
            pos += 8;
            left_size = MAX(left_size - 8, 0);
            now_flag = 0;
        } else
#endif
        if (left_size >= 4 || (left_size == 0 && size - left_size >= 4)) {
            uint32_t p_data = 0, q_data = 0, data = 0;
            if (p->size > pos) {
                p_data = *((uint32_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint32_t*)&q->data[pos]);
            }
            if ((p_data < q_data + pre_flag) || ((p_data == q_data) && (pre_flag == 1))) {
                now_flag = 1;
            }
            if (now_flag) {
                data = p_data + (UINT32_MAX - q_data) - pre_flag + 1;
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint32_t*)&p->data[pos]) = *((uint32_t*)&data);
            size -= 4;
            pos += 4;
            left_size = MAX(left_size - 4, 0);
            now_flag = 0;
        } else if (left_size >= 2 || (left_size == 0 && size - left_size >= 2)) {
            uint16_t p_data = 0, q_data = 0, data = 0;
            if (p->size > pos) {
                p_data = *((uint16_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint16_t*)&q->data[pos]);
            }
            if ((p_data < q_data + pre_flag) || ((p_data == q_data) && (pre_flag == 1))) {
                now_flag = 1;
            }
            if (now_flag) {
                data = p_data + (UINT16_MAX - q_data) - pre_flag + 1;
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint16_t*)&p->data[pos]) = *((uint16_t*)&data);
            size -= 2;
            pos += 2;
            left_size = MAX(left_size - 2, 0);
            now_flag = 0;
        } else {
            uint8_t p_data = 0, q_data = 0, data = 0;
            if (p->size > pos) {
                p_data = *((uint8_t*)&p->data[pos]);
            }
            if (q->size > pos) {
                q_data = *((uint8_t*)&q->data[pos]);
            }
            if ((p_data < q_data + pre_flag) || ((p_data == q_data) && (pre_flag == 1))) {
                now_flag = 1;
            }
            if (now_flag) {
                data = p_data + (UINT8_MAX - q_data) - pre_flag + 1;
                pre_flag = 1;
            } else {
                data = p_data - q_data - pre_flag;
                pre_flag = 0;
            }
            *((uint8_t*)&p->data[pos]) = *((uint8_t*)&data);
            size -= 1;
            pos += 1;
            left_size = MAX(left_size - 1, 0);
            now_flag = 0;
        }
    }

}

void bignum_mul(bignum_t* p, bignum_t* q, bignum_t* res) { // 采用KaraTsuba 大数相乘算法
#ifdef HAVE_UINT64_T
    if (p->size <= 4 && q->size <= 4) {
        uint64_t padded_p = 0, padded_q = 0;
        for (int32_t i = 0; i < p->size; i++) {
            ((uint8_t*)&padded_p)[i] = p->data[i];
        }
        for (int32_t i = 0; i < q->size; i++) {
            ((uint8_t*)&padded_q)[i] = q->data[i];
        }
        uint64_t sum = padded_p * padded_q;
        res->data = malloc(sizeof(sum));
        memcpy(res->data, &sum, sizeof(sum));
        res->size = sizeof(sum);
    }
#else
    if (p->size <= 2 && q->size <= 2) {
        uint32_t padded_p = 0, padded_q = 0;
        for (int32_t i = 0; i < p->size; i++) {
            ((uint8_t*)&padded_p)[i] = p->data[i];
        }
        for (int32_t i = 0; i < q->size; i++) {
            ((uint8_t*)&padded_q)[i] = q->data[i];
        }
        uint32_t sum = padded_p * padded_q;
        res->data = malloc(sizeof(sum));
        memcpy(res->data, &sum, sizeof(sum));
        res->size = sizeof(sum);
    }
#endif
    else { // 将大数p，q分别分为高位以及低位
        int32_t a_size = p->size / 2;
        int32_t c_size = q->size / 2;
        int32_t b_size = p->size - a_size;
        int32_t d_size = q->size - c_size;
        uint8_t* tmp_a = malloc(a_size);           // p的高位
        uint8_t* tmp_b = malloc(p->size - a_size); // p的低位
        uint8_t* tmp_c = malloc(c_size);           // q的高位
        uint8_t* tmp_d = malloc(q->size - c_size); // q的低位
        // 小端存储
        for (int32_t i = b_size, j = 0; i < p->size; i++, j++) {
            tmp_a[j] = p->data[i];
        }
        for (int32_t i = 0, j = 0; i < b_size; i++, j++) {
            tmp_b[j] = p->data[i];
        }
        for (int32_t i = d_size, j = 0; i < q->size; i++, j++) {
            tmp_c[j] = q->data[i];
        }
        for (int32_t i = 0, j = 0; i < d_size; i++, j++) {
            tmp_d[j] = q->data[i];
        }
        // 以下为实现KaraTsuba算法的具体步骤
        bignum_t a = {a_size, tmp_a};
        bignum_t b = {b_size, tmp_b};
        bignum_t c = {c_size, tmp_c};
        bignum_t d = {d_size, tmp_d};
        // res = a * c * 10 ^ (n / 2 + m / 2) + a * d * 10 ^ (n / 2 ) + b * c * 10 ^ (m / 2) + b * d;
        bignum_t z0;
        bignum_mul(&a, &c, &z0);
        bignum_t final0; // 高位 a * c
        bignum_lshift(&z0, (b_size + d_size) * 8, &final0);
        bignum_free(&z0);

        bignum_t z1;
        bignum_mul(&a, &d, &z1); // a * d
        bignum_t final1;
        bignum_lshift(&z1, b_size * 8, &final1); // a * d * 10 ^ (n / 2)
        bignum_free(&z1);
        free(tmp_a);

        bignum_t z2;
        bignum_mul(&b, &c, &z2); // b * c
        bignum_t final2;
        bignum_lshift(&z2, d_size * 8, &final2); // b * c * 10 ^ (m / 2)
        bignum_free(&z2);
        free(tmp_c);

        bignum_inc(&final1, &final2); // 相加,中位
        bignum_free(&final2);

        bignum_t final3;             // 低位
        bignum_mul(&b, &d, &final3); // b * d
        free(tmp_b);
        free(tmp_d);

        // 依次相加
        bignum_inc(&final0, &final1);
        bignum_free(&final1);
        bignum_add(&final0, &final3, res);
        bignum_free(&final3);
        bignum_free(&final0);
    }
}

// 将一个大数左移n位，返回新的结果，不改变原来的大数
void bignum_lshift(bignum_t* bn, int32_t n, bignum_t* res) {
    if (bn == NULL || n < 0) {
        return;
    }
    int32_t bytes = n / 8;
    int32_t bits = n % 8;
    INIT_BIGNUM(*res, bn->size + bytes + 1);
    if (res == NULL) {
        return;
    }
    uint8_t carry = 0;
    for (int32_t i = 0; i < bn->size; i++) {
        uint8_t val = bn->data[i];
        res->data[i + bytes] = (val << bits) | carry;
        carry = val >> (8 - bits);
    }
    memset(res->data, 0, bytes);
    res->data[bn->size + bytes] = carry;
}

// 将一个大数左移1位，就在原数上更改
void bignum_lshift_1(bignum_t* bn) {
    if (bn == NULL) {
        return;
    }
    uint8_t carry = 0;
    for (int32_t i = 0; i < bn->size - 1; i++) {
        uint8_t val = bn->data[i];
        bn->data[i] = (val << 1) | carry;
        carry = val >> 7;
    }
    if (bn->data[bn->size - 1] < 0x80) {
        bn->data[bn->size - 1] = (bn->data[bn->size - 1] << 1) | carry;
    } else {
        bn->data = realloc(bn->data, bn->size + 1);
        if (bn->data == NULL) {
            abort();
        }
        bn->data[bn->size - 1] = (bn->data[bn->size - 1] << 1) | carry;
        bn->data[bn->size] = 1;
        (bn->size)++;
    }
}

// 将一个大数右移n位，返回新的结果，不改变原来的大数
void bignum_rshift(bignum_t* bn, int32_t n, bignum_t* res) {
    if (bn == NULL || n < 0) {
        return;
    }
    int32_t bytes = n / 8;
    int32_t bits = n % 8;
    if (bytes >= bn->size) {
        INIT_BIGNUM(*res, 1);
        res->data[0] = 0;
        return;
    }
    INIT_BIGNUM(*res, bn->size - bytes);
    if (res == NULL) {
        return;
    }
    uint8_t carry = 0;
    for (int32_t i = bn->size - 1; i >= bytes; i--) {
        uint8_t val = bn->data[i];
        res->data[i - bytes] = (val >> bits) | carry;
        carry = val << (8 - bits);
    }
}

// 将一个大数右移1位，就在原数上更改
void bignum_rshift_1(bignum_t* bn) {
    if (bn == NULL) {
        return;
    }
    uint8_t carry = 0;
    for (int32_t i = bn->size - 1; i >= 0; i--) {
        uint8_t val = bn->data[i];
        bn->data[i] = (val >> 1) | carry;
        carry = val << 7;
    }
}

void bignum_div(bignum_t* a, bignum_t* b, bignum_t* quotient, bignum_t* remainder) {
    if (bignum_compare(a, b) < 0) {
        INIT_BIGNUM(*quotient, 1);
        quotient->data[0] = 0;
        bignum_cpy(remainder, a);
        return;
    }
    if (bignum_compare(a, b) == 0) {
        INIT_BIGNUM(*quotient, 1);
        quotient->data[0] = 1;
        INIT_BIGNUM(*remainder, 1);
        remainder->data[0] = 0;
        return;
    }
    int cnt = 0; // 移位数
    bignum_t tmp_a;
    bignum_t tmp_b;
    bignum_cpy(&tmp_a, a);
    bignum_cpy(&tmp_b, b);
    while (bignum_compare(&tmp_a, &tmp_b) >= 0) {
        bignum_lshift_1(&tmp_b);
        cnt++;
    }
    bignum_rshift_1(&tmp_b);
    int bytes;
    int bits;
    bytes = cnt / 8 + 1;
    bits = cnt % 8;
    INIT_BIGNUM(*quotient, bytes);
    memset(quotient->data, 0, bytes);
    while (bytes > 1 || bits > 0) {
        if (bits <= 0) {
            bytes--;
            bits += 8;
        }
        if (bignum_compare(&tmp_a, &tmp_b) >= 0) {
            bignum_dec(&tmp_a, &tmp_b);
            quotient->data[bytes - 1] |= 1 << (bits - 1);
        }
        bignum_rshift_1(&tmp_b);
        bits--;
    }
    bignum_cpy(remainder, &tmp_a);
    bignum_free(&tmp_a);
    bignum_free(&tmp_b);
}

// 大数除法，将商保存在bn中，不求余数
void bignum_self_div(bignum_t* a, bignum_t* b) {
    if (bignum_compare(a, b) < 0) {
        bignum_free(a);
        INIT_BIGNUM(*a, 1);
        a->data[0] = 0;
        return;
    }
    if (bignum_compare(a, b) == 0) {
        bignum_free(a);
        INIT_BIGNUM(*a, 1);
        a->data[0] = 1;
        return;
    }
    int cnt = 0; // 移位数
    bignum_t tmp_a;
    bignum_t tmp_b;
    bignum_cpy(&tmp_a, a);
    bignum_cpy(&tmp_b, b);
    while (bignum_compare(&tmp_a, &tmp_b) >= 0) {
        bignum_lshift_1(&tmp_b);
        cnt++;
    }
    bignum_rshift_1(&tmp_b);
    int bytes;
    int bits;
    bytes = cnt / 8 + 1;
    bits = cnt % 8;
    bignum_free(a);
    INIT_BIGNUM(*a, bytes);
    memset(a->data, 0, bytes);
    while (bytes > 1 || bits > 0) {
        if (bits <= 0) {
            bytes--;
            bits += 8;
        }
        if (bignum_compare(&tmp_a, &tmp_b) >= 0) {
            bignum_dec(&tmp_a, &tmp_b);
            a->data[bytes - 1] |= 1 << (bits - 1);
        }
        bignum_rshift_1(&tmp_b);
        bits--;
    }
    bignum_free(&tmp_a);
    bignum_free(&tmp_b);
}

void bignum_pow_mod(bignum_t* p, uint32_t e, bignum_t* n, bignum_t* res) {
    bignum_cpy(res, &bignum_one);
    if (e == 0) {
        bignum_cpy(res, &bignum_one);
        return;
    } else if (e == 1) {
        bignum_mod(p, n, res);
        return;
    }
    int size = 0;
    for (int i = 31; i >= 0; i--) {
        if ((e & (1 << i)) != 0) {
            size = i + 1;
            break;
        }
    }
    bignum_t tmp;
    bignum_cpy(&tmp, p);
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            bignum_t mid;
            bignum_mul(&tmp, &tmp, &mid);
            bignum_free(&tmp);
            bignum_trim(&mid);
            bignum_mod(&mid, n, &tmp);
            bignum_free(&mid);
        }
        if ((e & (1 << i)) != 0) {
            bignum_t mid;
            bignum_mul(&tmp, res, &mid);
            bignum_free(res);
            bignum_trim(&mid);
            bignum_mod(&mid, n, res);
            bignum_free(&mid);
        }
    }
    bignum_free(&tmp);
}

void bignum_pow_mod_bignum(bignum_t* p, bignum_t* e, bignum_t* n, bignum_t* res) {
    bignum_cpy(res, &bignum_one);

    if (bignum_compare(e, &bignum_zero) == 0) {
        bignum_cpy(res, &bignum_one);
        return;
    } else if (bignum_compare(e, &bignum_one) == 0) {
        bignum_mod(p, n, res);
        return;
    }
    
    bignum_t tmp, i, size, shift_e;
    bignum_cpy(&tmp, p);
    bignum_cpy(&shift_e, e);
    bignum_trim(&shift_e);
    
    int zeros = 0;
    for (int i = 7; i > 0; i--) {
        if ((shift_e.data[shift_e.size - 1] & (1 << i)) == 0) {
            zeros++;
        } else {
            break;
        }
    }
    bignum_set32(shift_e.size * 8 - zeros, &size);
    
    int first = 1;
    for (bignum_cpy(&i, &bignum_zero); bignum_compare(&i, &size) < 0; bignum_inc(&i, &bignum_one)) {
        if (!first) {
            bignum_t mid;
            bignum_mul(&tmp, &tmp, &mid);
            bignum_free(&tmp);
            bignum_trim(&mid);
            bignum_mod(&mid, n, &tmp);
            bignum_free(&mid);
        }
        first = 0;
        if ((shift_e.data[0] & 1) == 1) {
            bignum_t mid;
            bignum_mul(&tmp, res, &mid);
            bignum_free(res);
            bignum_trim(&mid);
            bignum_mod(&mid, n, res);
            bignum_free(&mid);
        }
        bignum_rshift_1(&shift_e);
    }
    bignum_free(&tmp);
    bignum_free(&i);
    bignum_free(&size);
    bignum_free(&shift_e);
}

// 求大数模，不改变原来大数
void bignum_mod(bignum_t* a, bignum_t* b, bignum_t* res) {
    if (bignum_compare(a, b) < 0) {
        bignum_cpy(res, a);
        return;
    }
    if (bignum_compare(a, b) == 0) {
        INIT_BIGNUM(*res, 1);
        res->data[0] = 0;
        return;
    }
    int cnt = 0; // 移位数
    bignum_t tmp_a;
    bignum_t tmp_b;
    bignum_cpy(&tmp_a, a);
    bignum_cpy(&tmp_b, b);
    while (bignum_compare(&tmp_a, &tmp_b) >= 0) {
        bignum_lshift_1(&tmp_b);
        cnt++;
    }
    bignum_rshift_1(&tmp_b);
    int bytes;
    int bits;
    bytes = cnt / 8 + 1;
    bits = cnt % 8;
    while (bytes > 1 || bits > 0) {
        if (bits <= 0) {
            bytes--;
            bits += 8;
        }
        if (bignum_compare(&tmp_a, &tmp_b) >= 0) {
            bignum_dec(&tmp_a, &tmp_b);
        }
        bignum_rshift_1(&tmp_b);
        bits--;
    }
    bignum_cpy(res, &tmp_a);
    bignum_free(&tmp_a);
    bignum_free(&tmp_b);
}

// 求大数模，把结果保存在a中
void bignum_self_mod(bignum_t* a, bignum_t* b) {
    if (bignum_compare(a, b) < 0) {
        return;
    }
    if (bignum_compare(a, b) == 0) {
        bignum_free(a);
        INIT_BIGNUM(*a, 1);
        a->data[0] = 0;
        return;
    }
    int cnt = 0; // 移位数
    bignum_t tmp_a;
    bignum_t tmp_b;
    bignum_cpy(&tmp_a, a);
    bignum_cpy(&tmp_b, b);
    while (bignum_compare(&tmp_a, &tmp_b) >= 0) {
        bignum_lshift_1(&tmp_b);
        cnt++;
    }
    bignum_rshift_1(&tmp_b);
    int bytes;
    int bits;
    bytes = cnt / 8 + 1;
    bits = cnt % 8;
    while (bytes > 1 || bits > 0) {
        if (bits <= 0) {
            bytes--;
            bits += 8;
        }
        if (bignum_compare(&tmp_a, &tmp_b) >= 0) {
            bignum_dec(&tmp_a, &tmp_b);
        }
        bignum_rshift_1(&tmp_b);
        bits--;
    }
    bignum_free(a);
    bignum_cpy(a, &tmp_a);
    bignum_free(&tmp_a);
    bignum_free(&tmp_b);
}

void bignum_set32(int32_t a, bignum_t* res) {
    INIT_BIGNUM(*res, 4);
    memcpy(res->data, &a, 4);
}

void bignum_trim(bignum_t* num) {
    uint8_t* ptr = &num->data[num->size - 1];
    while (*ptr == 0 && num->size != 1) {
        num->size--;
        ptr--;
    }
}

// 求大数最大公因子
void bignum_gcd(bignum_t* a, bignum_t* b, bignum_t* res) {
    bignum_t tmp_a,tmp_b,c;
    bignum_cpy(&tmp_a, a);
    bignum_cpy(&tmp_b, b);
    while(bignum_compare(b, &bignum_zero) != 0) {
        // c = a % b
        bignum_mod(&tmp_a, &tmp_b, &c);
        // a = b
        bignum_free(&tmp_a);
        bignum_cpy(&tmp_a, &tmp_b);
        // b = c
        bignum_free(&tmp_b);
        bignum_cpy(&tmp_b, &c);
        bignum_free(&c);
    }
    bignum_cpy(res, &tmp_a);
    bignum_free(&bignum_zero);
    bignum_free(&tmp_a);
    bignum_free(&tmp_b);
}

// 求大数模逆
int bignum_mod_inv(bignum_t* a, bignum_t* mod, bignum_t* res) {
    sbignum_t x, y, u, v, g, h;
    sbignum_t q, t;
    sbignum_t tmp1, tmp2;
    // x = 0
    bignum_cpy(&x.num, &bignum_zero);x.neg = 0; // 整数x，满足 a * x + b * y = gcd(a, b)
    // y = 1
    bignum_cpy(&y.num, &bignum_one);y.neg = 0; // 整数y, 满足 a * x + b * y = gcd(a, b)
    // u = 1
    bignum_cpy(&u.num, &bignum_one);u.neg = 0; // 整数u，用来存储x的前一个值
    // v = 0
    bignum_cpy(&v.num, &bignum_zero);v.neg = 0; //整数v，用来存储y的前一个值
    // g = a
    bignum_cpy(&g.num, a);g.neg = 0; //整数g，用来存储a和m的最大公因数
    // h = m
    bignum_cpy(&h.num, mod);h.neg = 0; // 整数h，用来存储m的值

    while(bignum_compare(&g.num, &bignum_zero) != 0) {
        // g 和 h 不可能小于0
        // q = h / g
        // t = h % g
        bignum_div(&h.num, &g.num, &q.num, &t.num);
        q.neg = 0;
        t.neg = 0;

        // h = g
        sbignum_free(&h);sbignum_cpy(&h, &g);
        // g = t
        sbignum_free(&g);sbignum_cpy(&g, &t);
        // t = x
        sbignum_free(&t);sbignum_cpy(&t, &x);
        // x = u - q * x
        sbignum_mul(&q, &x, &tmp1);
        bignum_trim(&tmp1.num);
        sbignum_sub(&u, &tmp1, &tmp2);
        sbignum_free(&x);
        sbignum_cpy(&x, &tmp2);
        sbignum_free(&tmp1);
        sbignum_free(&tmp2);
        // u = t
        sbignum_free(&u);sbignum_cpy(&u, &t);
        // t = y
        sbignum_free(&t);sbignum_cpy(&t, &y);
        //y = v - q * y
        sbignum_mul(&q, &y, &tmp1);
        bignum_trim(&tmp1.num);
        sbignum_sub(&v, &tmp1, &tmp2);
        sbignum_free(&y);
        sbignum_cpy(&y, &tmp2);
        sbignum_free(&tmp1);
        sbignum_free(&tmp2);
        // v = t
        sbignum_free(&v);sbignum_cpy(&v, &t);

        sbignum_free(&q);
        sbignum_free(&t);
    }

    // 如果 h != 1，则不存在模逆
    if(bignum_compare(&h.num, &bignum_one) != 0) {
        sbignum_free(&x);
        sbignum_free(&y);
        sbignum_free(&u);
        sbignum_free(&v);
        sbignum_free(&g);
        sbignum_free(&h);
        return 1;
    }

    // 返回模逆结果
    bignum_cpy(&tmp1.num, mod);tmp1.neg = 0;
    // res = (v + m) % m
    sbignum_add(&v, &tmp1, &tmp2); // 这里确保 tmp2 > 0
    sbignum_free(&tmp1);
    bignum_mod(&tmp2.num, mod, &tmp1.num);
    bignum_cpy(res, &tmp1.num);

    sbignum_free(&x);
    sbignum_free(&y);
    sbignum_free(&u);
    sbignum_free(&v);
    sbignum_free(&g);
    sbignum_free(&h);
    sbignum_free(&tmp1);
    sbignum_free(&tmp2);
    return 0;
}
